package leetcode.p27删除元素;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
//        int [] nums = new int []{2,3,3,2};
//        int target = 3;
//        removeElement(nums,target);
//        for (int i: nums){
//            System.out.println(i);
//        }
        int [] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));

    }
    public static int removeElement(int[] nums, int val) {
        int len = nums.length;
        int i = 0;
        while(i < len) {
            if(nums[i] == val) {
                nums[i] = nums[len-1];
                len--;
            }else {
                i++;
            }
        }
        return len;
    }

    /***
     * 找出数组中的数值最大的子数组。
     * @param A
     * @return
     */
    public static int maxSubArray(int[] A) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i=0; i < A.length; i++) {
            if(sum < 0) {
                sum = A[i];
            }else {
                sum += A[i];
            }
            if(sum > max)
                max = sum;
        }
       return max;
    }


    /***
     * 数组组成的一个数字，然后加1
     * Input: digits = [1,2,3]
     * Output: [1,2,4]
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {

        int n = digits.length;
        for(int i=n-1; i>=0; i--) {
            if(digits[i] < 9) { //如果小于9直接加1返回。
                digits[i]++;
                return digits;
            }
            //等于9 就变成0
            digits[i] = 0;
        }
        //最后还没有返回走到这里，可能这个数组是这样的 [9,9,9,9] ,那么就增加一位
        int[] newNumber = new int [n+1];
        newNumber[0] = 1;

        return newNumber;
    }

    /***
     * 买卖股票1
     * Input: prices = [7,1,5,3,6,4]
     * Output: 7
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, max = 0;
        for (int price : prices) {
            min = Math.min(price,min);
            max = Math.max(max,price-min);
        }
        return max;
    }

    /***
     * 买卖股票2，可多次买入卖出
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int res = 0;
        for(int i=0;i < prices.length-1; i++) {
            if(prices[i] < prices[i+1]) {
                res += prices[i+1]-prices[i];
            }
        }
        return res;
    }

    /***
     * 167
     * 数组排序，给出目标值，找到两个元素的和是目标值的。元素不会被重复使用
     * Input: numbers = [2,7,11,15], target = 9
     * Output: [1,2]
     * Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
     */
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int left = 0, right = numbers.length - 1;
        if(numbers == null || numbers.length < 2) return res;
        while(left < right) {
            int v = numbers[left] + numbers[right];
            if(v == target) {
                res[0] = left+1;
                res[1] = right + 1;
                return res;
            }else if(v > target) {
                right--;
            }else {
                left++;
            }
        }
        return res;
    }

    /***
     * 219
     * 滑动窗口思想。 k就是窗口大小;遍历的数据超过窗口大小了，就删除之前的数据，然后再将新数据放进去
     * Input: nums = [1,2,3,1], k = 3
     * Output: true
     *
     * 【1,2,3,1,2,3】  k = 2
     *  false
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(i > k) set.remove(nums[i-k-1]);
            if(!set.add(nums[i])) return true;
        }
        return false;
    }

    /***
     * Input: nums = [0,1,2,4,5,7]
     * Output: ["0->2","4->5","7"]
     * Explanation: The ranges are:
     * [0,2] --> "0->2"
     * [4,5] --> "4->5"
     * [7,7] --> "7"
     * @param nums
     * @return
     */
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        int pos = 0;
        while(pos < nums.length) {
            int temp = pos;
            StringBuilder it = new StringBuilder(""+nums[pos]);
            while(pos+1 < nums.length && nums[pos] +1 == nums[pos+1])
                pos++;
            if(temp != pos)
                it.append("->").append(nums[pos]);
            list.add(it.toString());
            pos++;
        }
        return list;
    }
}
